A. Chagrov, M. Zakharyaschev; "Modal Logic" Chapter.1 読書録1
参考文献
メモ
これは私は全く知らなかった性質(特にHalldén完全性とPost完全)なのだが,論理一般に対して次の性質と定理がある.既知のものも多少定義に揺らぎがあるので全部まとめる. ただし表記は全然違う.今後は改める
メモ
論理を$ \Lambdaとする.
通読していないからわからないが,一般に全ての意味論的にトートロジーとして定義されるだろうと思われる.
すなわち擬似的に書くなら,$ \Lambda := \{ \varphi \in \mathrm{Form}_{\mathscr{L}_\Lambda} \mid \models \varphi \}のことを指す(と思われる).
$ \mathrm{Form}_{\mathscr{L}_\Lambda}は($ \Lambdaの為の)言語$ \mathscr{L}_\Lambdaの論理式全体の集合を指す.
古典命題論理$ \mathbf{cPL} := \{ \varphi \in \mathrm{Form}_{\mathscr{L}_\mathbf{PL}} \mid \models \varphi \}とする.
$ \Lambdaが無矛盾とは,$ \Lambda \neq \mathrm{Form}_{\mathscr{L}_\Lambda}であることを指す.
$ \LambdaがPost完全であるとは,$ \Lambdaが無矛盾かつ,無矛盾な$ \Lambdaの真の拡大が存在しないことを指す. proof
$ \mathbf{cPL} \sub \mathbf{cPL} \cup \{\varphi\}となる$ \varphi \notin \mathbf{cPL}が存在するとして,$ \mathbf{cPL} \cup \{\varphi\}は無矛盾とする.
前提より$ V(\varphi) = 0となる付値$ Vが存在する(任意の付値$ Vで$ V(\varphi) = 1から$ \varphi \in \mathbf{cPL}となっておかしいから)のでそのような$ Vを取ってくる.
このときどのような$ Vに関しても$ V(\varphi \to \bot) = 1となる.
すると$ \varphi \to \bot \in \mathbf{cPL}であり,$ \varphi \to \bot \in \mathbf{cPL} \cup \{\varphi\}となる.
今$ \varphi \in \mathbf{cPL} \cup \{\varphi\}とモーダス・ポネンスより$ \bot \in \mathbf{cPL} \cup \{\varphi\}だから$ \mathbf{cPL} \cup \{\varphi\}は無矛盾ではなくなる.しかしこれは前提に反するためおかしい. よってそのような$ \varphiは取ってこれない:すなわち真の拡大は構成できない.❏ #TODO 代入の概念を定義しないと行けないので一旦省略. 論理式の集合$ \Gamma \sube \mathrm{Form}_\mathscr{L}が存在して(この$ \Gammaは独立的公理集合と呼ぶ),モーダス・ポネンス(と代入規則)による閉包が$ \Lambdaと一致し,かつ$ \Gammaの真の部分集合のそのような閉包は$ \Lambdaと一致しないことを指す. memoおそらく次章以降のことを考えるとネセシテーションといった推論規則も絡むと思われるので全ての推論規則の閉包とでも言えば良いと思われる. もし$ \varphi \to \psi \in \Lambdaであるとき,$ \varphi,\psiのどちらにも現れる命題変項だけを持ち,$ \varphi \to \xi \in \Lambdaかつ$ \xi \to \psi \in \Lambdaとなる論理式$ \xiが存在することを指す.$ \xiは$ \varphi,\psiの補間という.
proof
$ \LambdaがHalldén完全性であるとは,共通の命題変項が存在しない論理式$ \varphi,\psiについて,$ \varphi \lor \psi \in \Lambda$ \iff$ \varphi \in \Lambdaまたは$ \psi \in \Lambdaとなることを指す. proof
対偶を示す.
$ \varphi,\psi \notin \mathbf{cPL}とする.このとき$ V_1(\varphi) = 0となる$ V_1と$ V_2(\psi) = 0となる$ V_2が存在するので取ってくる.
付値$ V(p) = 1 \iff p \in \mathrm{Sub}(\varphi) ~\&~ V_1(p) = 1 ~~\text{or}~~ p \in \mathrm{Sub}(\psi) ~\&~ V_2(p) = 1と定義する.
この$ Vでは$ V(\varphi) = 0と$ V(\psi) = 0となるので$ V(\varphi \lor \psi) = 0すなわち$ \varphi \lor \psi \notin \mathbf{cPL}である.❏ $ \Lambdaが選言特性を持つとは,任意の論理式$ \varphi,\psiに対して$ \varphi \lor \psi \in \Lambda$ \iff$ \varphi \in \Lambdaまたは$ \psi \in \Lambdaとなることを指す. $ \bf cPLは選言特性を持たない.
remark
明らかだが,次が成り立つ.